package greddy;

public class _09_135_分发糖果 {
    public static int candy(int[] ratings) {
    	int candy[] = new int[ratings.length];
    	int count = ratings.length;
    	// 先判断当前值是否比左边的大，是则candy=左边值+1
    	for(int i = 1; i < ratings.length; i++) {
    		if(ratings[i] > ratings[i - 1]) {
    			candy[i] = candy[i - 1] + 1;
    		}
    	}
    	// 再判断当前值是否比右边的大，是则candy=右边值+1
    	// 由于我们这里取的是右边candy的值+1，所以需要从后往前，这样右边的candy才是经过计算的
    	// 由于前面已经判断过一轮，所以candy是变化过的，可能之前的值更大，所以需要取max
    	for(int i = ratings.length - 2; i >= 0; i--) {
    		if(ratings[i] > ratings[i+1]) {
    			candy[i] = Math.max(candy[i], candy[i + 1] + 1);
    		}
    	}
    	
    	for(int i = 0; i < candy.length; i++) {
    		count += candy[i];
    	}
    	
    	return count;
    }
    
    public static void main(String[] args) {
    	int[] ratings = {1,0,2}; // 13
    	System.out.println(candy(ratings));
	}
}
